Informed Lifting for Message%2DPassing.
Lifted inference, handling whole sets of indistinguishable objects together, is critical to the effective application of probabilistic relational models to realistic real world tasks. Recently, lifted belief propagation (LBP) has been proposed as an efficient approximate solution of this inference problem. It runs a modified BP on a lifted network where nodes have been grouped together if they have — roughly speaking — identical computation trees, the tree-structured unrolling of the underlying graph rooted at the nodes. In many situations, this purely syntactic criterion is too pessimistic: message errors decay along paths. Intuitively, for a long chain graph with weak edge potentials, distant nodes will send and receive identical messages yet their computation trees are quite different. To overcome this, we propose iLBP, a novel, easy-to-implement, informed LBP approach that interleaves lifting and modified BP iterations. In turn, we can efficiently monitor the true BP messages sent and received in each iteration and group nodes accordingly. As our experiments show, iLBP can yield significantly faster more lifted network while not degrading performance. Above all, we show that iLBP is faster than BP when solving the problem of distributing data to a large network, an important real-world application where BP is faster than uninformed LBP.
Symbolic Dynamic Programming for First%2Dorder POMDPs.
Partially-observable Markov decision processes (POMDPs) provide a powerful model for sequential decision-making problems with partially-observed state and are known to have (approximately) optimal dynamic programming solutions. Much work in recent years has focused on improving the efficiency of these dynamic programming algorithms by exploiting symmetries and factored or relational representations. In this work, we show that it is also possible to exploit the full expressive power of first-order quantification to achieve state, action, and observation abstraction in a dynamic programming solution to relationally specified POMDPs. Among the advantages of this approach are the ability to maintain compact value function representations, abstract over the space of potentially optimal actions, and automatically derive compact conditional policy trees that minimally partition relational observation spaces according to distinctions that have an impact on policy values. This is the first lifted relational POMDP solution that can optimally accommodate actions with a potentially infinite relational space of observation outcomes.
Yes we can simplex volume maximization for descriptive web%2Dscale matrix factorization.
Matrix factorization methods are among the most common techniques for detecting latent components in data. Popular examples include the Singular Value Decomposition or Nonnegative Matrix Factorization. Unfortunately, most methods suffer from high computational complexity and therefore do not scale to massive data. In this paper, we present a linear time algorithm for the factorization of gigantic matrices that iteratively yields latent components. We consider a constrained matrix factorization s.t. the latent components form a simplex that encloses most of the remaining data. The algorithm maximizes the volume of that simplex and thereby reduces the displacement of data from the space spanned by the latent components. Hence, it also lowers the Frobenius norm, a common criterion for matrix factorization quality. Our algorithm is efficient, well-grounded in distance geometry, and easily applicable to matrices with billions of entries. In addition, the resulting factors allow for an intuitive interpretation of data: every data point can now be expressed as a convex combination of the most extreme and thereby often most descriptive instances in a collection of data. Extensive experimental validations on web-scale data, including 80 million images and 1.5 million twitter tweets, demonstrate superior performance compared to related factorization or clustering techniques.
Exploration in Relational Worlds.
Abstract. One of the key problems in model-based reinforcement learning is balancing exploration and exploitation. Another is learning and acting in large relational domains, in which there is a varying number of objects and relations between them. We provide a solution to exploring large relational Markov decision processes by developing relational extensions of the concepts of the Explicit Explore or Exploit (E 3) algorithm. A key insight is that the inherent generalization of learnt knowledge in the relational representation has profound implications also on the exploration strategy: what in a propositional setting would be considered a novel situation and worth exploration may in the relational setting be an instance of a well-known context in which exploitation is promising. Our experimental evaluation shows the effectiveness and benefit of relational exploration over several propositional benchmark approaches on noisy 3D simulated robot manipulation problems. 1
Exploiting Causal Independence in Markov Logic Networks Combining Undirected and Directed Models.
Abstract. A new method is proposed for compiling causal independencies into Markov logic networks (MLNs). A MLN can be viewed as compactly representing a factorization of a joint probability into the product of a set of factors guided by logical formulas. We present a notion of causal independence that enables one to further factorize the factors into a combination of even smaller factors and consequently obtain a finer-grain factorization of the joint probability. The causal independence lets us specify the factor in terms of weighted, directed clauses and operators, such as “or”, “sum ” or “max”, on the contribution of the variables involved in the factors, hence combining both undirected and directed knowledge. Our experimental evaluations shows that making use of the finer-grain factorization provided by causal independence can improve quality of parameter learning in MLNs. 1
Exploiting Causal Independence in Markov Logic Networks Combining Undirected and Directed Models.
Abstract. A new method is proposed for compiling causal independencies into Markov logic networks (MLNs). A MLN can be viewed as compactly representing a factorization of a joint probability into the product of a set of factors guided by logical formulas. We present a notion of causal independence that enables one to further factorize the factors into a combination of even smaller factors and consequently obtain a finer-grain factorization of the joint probability. The causal independence lets us specify the factor in terms of weighted, directed clauses and operators, such as “or”, “sum ” or “max”, on the contribution of the variables involved in the factors, hence combining both undirected and directed knowledge. Our experimental evaluations shows that making use of the finer-grain factorization provided by causal independence can improve quality of parameter learning in MLNs. 1
Topic Models Conditioned on Relations.
Abstract. Latent Dirichlet allocation is a fully generative statistical language model that has been proven to be successful in capturing both the content and the topics of a corpus of documents. Recently, it was even shown that relations among documents such as hyper-links or citations allow one to share information between documents and in turn to improve topic generation. Although fully generative, in many situations we are actually not interested in predicting relations among documents. In this paper, we therefore present a Dirichlet-multinomial nonparametric regression topic model that includes a Gaussian process prior on joint document and topic distributions that is a function of document relations. On networks of scientific abstracts and of Wikipedia documents we show that this approach meets or exceeds the performance of several baseline topic models. 1
Fast Active Exploration for Link%2DBased Preference Learning Using Gaussian Processes.
Abstract. In preference learning, the algorithm observes pairwise relative judgments (preference) between items as training data for learning an ordering of all items. This is an important learning problem for applications where absolute feedback is difficult to elicit, but pairwise judgments are readily available (e.g., via implicit feedback [13]). While it was already shown that active learning can effectively reduce the number of training pairs needed, the most successful existing algorithms cannot generalize over items or queries. Considering web search as an example, they would need to learn a separate relevance score for each document-query pair from scratch. To overcome this inefficiency, we propose a link-based active preference learning method based on Gaussian Processes (GPs) that incorporates dependency information from both feature-vector representations as well as relations. Specifically, to meet the requirement on computational efficiency of active exploration, we introduce a novel incremental update method that scales as well as the non-generalizing models. The proposed algorithm is evaluated on datasets for information retrieval, showing that it learns substantially faster than algorithms that cannot model dependencies. 1
Kernelized map matching.

Self%2DTaught Decision Theoretic Planning with First Order Decision Diagrams.

Beyond 2D%2Dgrids a dependence maximization view on image browsing.

Learning Preferences with Hidden Common Cause Relations.
Abstract. Gaussian processes have successfully been used to learn preferences among entities as they provide nonparametric Bayesian approaches for model selection and probabilistic inference. For many entities encountered in real-world applications, however, there are complex relations between them. In this paper, we present a preference model which incorporates information on relations among entities. Specifically, we propose a probabilistic relational kernel model for preference learning based on Silva et al.’s mixed graph Gaussian processes: a new prior distribution, enhanced with relational graph kernels, is proposed to capture the correlations between preferences. Empirical analysis on the LETOR datasets demonstrates that relational information can improve the performance of preference learning. 1
Stacked Gaussian Process Learning.

Convex Non%2Dnegative Matrix Factorization in the Wild.
Abstract—Non-negative matrix factorization (NMF) has recently received a lot of attention in data mining, information retrieval, and computer vision. It factorizes a non-negative input matrix V into two non-negative matrix factors V = WH such that W describes ”clusters ” of the datasets. Analyzing genotypes, social networks, or images, it can be beneficial to ensure V to contain meaningful “cluster centroids”, i.e., to restrict W to be convex combinations of data points. But how can we run this convex NMF in the wild, i.e., given millions of data points? Triggered by the simple observation that each data point is a convex combination of vertices of the data convex hull, we propose to restrict W further to be vertices of the convex hull. The benefits of this convex-hull NMF approach are twofold. First, the expected size of the convex hull of, for example, n random Gaussian points in the plane is Ω (  √ log n), i.e., the candidate set typically grows much slower than the data set. Second, distance preserving low-dimensional embeddings allow one to compute candidate vertices efficiently. Our extensive experimental evaluation shows that convex-hull NMF compares favorably to convex NMF for large data sets both in terms of speed and reconstruction quality. Moreover, we show that our method can easily be applied to large-scale, real-world data sets, in our case consisting of 1.6 million images respectively 150 million votes on World of Warcraft R ○ guilds. Keywords-data mining; matrix decomposition; data handling; non negative matrix factorization; archetypal analysis; social network analysis; I.
Kernel Conditional Quantile Estimation via Reduction Revisited.
Abstract—Quantile regression refers to the process of estimating the quantiles of a conditional distribution and has many important applications within econometrics and data mining, among other domains. In this paper, we show how to estimate these conditional quantile functions within a Bayes risk minimization framework using a Gaussian process prior. The resulting non-parametric probabilistic model is easy to implement and allows non-crossing quantile functions to be enforced. Moreover, it can directly be used in combination with tools and extensions of standard Gaussian Processes such as principled hyperparameter estimation, sparsification, and quantile regression with input-dependent noise rates. No existing approach enjoys all of these desirable properties. Experiments on benchmark datasets show that our method is competitive with state-of-the-art approaches. Keywords-Regression; Quantile Regression; Gaussian Processes; I.
Multi%2DRelational Learning with Gaussian Processes.
Due to their flexible nonparametric nature, Gaussian process models are very effective at solving hard machine learning problems. While existing Gaussian process models focus on modeling one single relation, we present a generalized GP model, named multi-relational Gaussian process model, that is able to deal with an arbitrary number of relations in a domain of interest. The proposed model is analyzed in the context of bipartite, directed, and undirected univariate relations. Experimental results on real-world datasets show that exploiting the correlations among different entity types and relations can indeed improve prediction performance. 1
Generalized First Order Decision Diagrams for First Order Markov Decision Processes.
First order decision diagrams (FODD) were recently introduced as a compact knowledge representation expressing functions over relational structures. FODDs represent numerical functions that, when constrained to the Boolean range, use only existential quantification. Previous work developed a set of operations over FODDs, showed how they can be used to solve relational Markov decision processes (RMDP) using dynamic programming algorithms, and demonstrated their success in solving stochastic planning problems from the International Planning Competition in the system FODD-Planner. A crucial ingredient of this scheme is a set of operations to remove redundancy in decision diagrams, thus keeping them compact. This paper makes three contributions. First, we introduce Generalized FODDs (GFODD) and combination algorithms for them, generalizing FODDs to arbitrary quantification. Second, we show how GFODDs can be used in principle to solve RMDPs with arbitrary quantification, and develop a particularly promising case where an arbitrary number of existential quantifiers is followed by an arbitrary number of universal quantifiers. Third, we develop a new approach to reduce FODDs and GFODDs using model checking. This yields a reduction that is complete for FODDs and provides a sound reduction procedure for GFODDs. 1
ILP%2C the Blind%2C and the Elephant Euclidean Embedding of Co%2Dproven Queries.
Abstract. Relational data is complex. This complexity makes one of the basic steps of ILP difficult: understanding the data and results. If the user cannot easily understand it, he draws incomplete conclusions. The situation is very much as in the parable of the blind men and the elephant that appears in many cultures. In this tale the blind work independently and with quite different pieces of information, thereby drawing very different conclusions about the nature of the beast. In contrast, visual representations make it easy to shift from one perspective to another while exploring and analyzing data. This paper describes a method for embedding interpretations and queries into a single, common Euclidean space based on their co-proven statistics. We demonstrate our method on real-world datasets showing that ILP results can indeed be captured at a glance. 1
ILP%2C the Blind%2C and the Elephant Euclidean Embedding of Co%2Dproven Queries.
Abstract. Relational data is complex. This complexity makes one of the basic steps of ILP difficult: understanding the data and results. If the user cannot easily understand it, he draws incomplete conclusions. The situation is very much as in the parable of the blind men and the elephant that appears in many cultures. In this tale the blind work independently and with quite different pieces of information, thereby drawing very different conclusions about the nature of the beast. In contrast, visual representations make it easy to shift from one perspective to another while exploring and analyzing data. This paper describes a method for embedding interpretations and queries into a single, common Euclidean space based on their co-proven statistics. We demonstrate our method on real-world datasets showing that ILP results can indeed be captured at a glance. 1
Probabilistic
Abstract. This paper presents a Bayesian method for constructing probabilistic networks from databases. In particular, we focus on constructing Bayesian belief networks. Potential applications include computer-assisted hypothesis testing, automated scientific discovery, and automated construction of probabilistic expert systems. We extend the basic method to handle missing data and hidden (latent) variables. We show how to perform probabilistic inference by averaging over the inferences of multiple belief networks. Results are presented of a preliminary evaluation of an algorithm for constructing a belief network from a database of cases. Finally, we relate the methods in this paper to previous work, and we discuss open problems.
Probabilistic Inductive Logic Programming %2D Theory and Applications

Lifted Probabilistic Inference with Counting Formulas.
Lifted inference algorithms exploit repeated structure in probabilistic models to answer queries efficiently. Previous work such as de Salvo Braz et al.’s first-order variable elimination (FOVE) has focused on the sharing of potentials across interchangeable random variables. In this paper, we also exploit interchangeability within individual potentials by introducing counting formulas, which indicate how many of the random variables in a set have each possible value. We present a new lifted inference algorithm, C-FOVE, that not only handles counting formulas in its input, but also creates counting formulas for use in intermediate potentials. C-FOVE can be described succinctly in terms of six operators, along with heuristics for when to apply them. Because counting formulas capture dependencies among large numbers of variables compactly, C-FOVE achieves asymptotic speed improvements compared to FOVE.
Parameter Learning in Probabilistic Databases A Least Squares Approach.
Abstract. We introduce the problem of learning the parameters of the probabilistic database ProbLog. Given the observed success probabilities of a set of queries, we compute the probabilities attached to facts that have a low approximation error on the training examples as well as on unseen examples. Assuming Gaussian error terms on the observed success probabilities, this naturally leads to a least squares optimization problem. Our approach, called LeProbLog, is able to learn both from queries and from proofs and even from both simultaneously. This makes it flexible and allows faster training in domains where the proofs are available. Experiments on real world data show the usefulness and effectiveness of this least squares calibration of probabilistic databases. 1
Nonstationary Gaussian Process Regression Using Point Estimates of Local Smoothness.
Abstract. Gaussian processes using nonstationary covariance functions are a powerful tool for Bayesian regression with input-dependent smoothness. A common approach is to model the local smoothness by a latent process that is integrated over using Markov chain Monte Carlo approaches. In this paper, we demonstrate that an approximation that uses the estimated mean of the local smoothness yields good results and allows one to employ efficient gradient-based optimization techniques for jointly learning the parameters of the latent and the observed processes. Extensive experiments on both synthetic and real-world data, including challenging problems in robotics, show the relevance and feasibility of our approach. 1
Boosting Relational Sequence Alignments.
The task of aligning sequences arises in many applications. Classical dynamic programming approaches require the explicit state enumeration in the reward model. This is often impractical: the number of states grows very quickly with the number of domain objects and relations among these objects. Relational sequence alignment aims at exploiting symbolic structure to avoid the full enumeration. This comes at the expense of a more complex reward model selection problem: virtually infinitely many abstraction levels have to be explored. In this paper, we apply gradientbased boosting to leverage this problem. Specifically, we show how to reduce the learning problem to a series of relational regressions problems. The main benefit of this is that interactions between states variables are introduced only as needed, so that the potentially infinite search space is not explicitly considered. As our experimental results show, this boosting approach can significantly improve upon established results in challenging applications. 1.
Non%2Dparametric policy gradients a unified treatment of propositional and relational domains.
Policy gradient approaches are a powerful instrument for learning how to interact with the environment. Existing approaches have focused on propositional and continuous domains only. Without extensive feature engineering, it is difficult – if not impossible – to apply them within structured domains, in which e.g. there is a varying number of objects and relations among them. In this paper, we describe a non-parametric policy gradient approach – called NPPG – that overcomes this limitation. The key idea is to apply Friedmann’s gradient boosting: policies are represented as a weighted sum of regression models grown in an stage-wise optimization. Employing off-the-shelf regression learners, NPPG can deal with propositional, continuous, and relational domains in a unified way. Our experimental results show that it can even improve on established results. 1.
Logical Hierarchical Hidden Markov Models for Modeling User Activities.
Abstract. Hidden Markov Models (HMM) have been successfully used in applications such as speech recognition, activity recognition, bioinformatics etc. There have been previous attempts such as Hierarchical HMMs and Abstract HMMs to elegantly extend HMMs at multiple levels of temporal abstraction (for example to represent the user’s activities). Similarly, there has been previous work such as Logical HMMs on extending HMMs to domains with relational structure. In this work we develop a representation that naturally combines the power of both relational and hierarchical models in the form of Logical Hierarchical Hidden Markov Models (LoHiHMMs). LoHiHMMs inherit the compactness of representation from Logical HMMs and the tractability of inference from Hierarchical HMMs. We outline two inference algorithms: one based on grounding the LoHiHMM to a propositional HMM and the other based on particle filtering adapted for this setting. We present the results of our experiments with the model in two simulated domains. 1
SRL without Tears An ILP Perspective.

Learning predictive terrain models for legged robot locomotion.
Abstract — Legged robots require accurate models of their environment in order to plan and execute paths. We present a probabilistic technique based on Gaussian processes that allows terrain models to be learned and updated efficiently using sparse approximation techniques. The major benefit of our terrain model is its ability to predict elevations at unseen locations more reliably than alternative approaches, while it also yields estimates of the uncertainty in the prediction. In particular, our nonstationary Gaussian process model adapts its covariance to the situation at hand, allowing more accurate inference of terrain height at points that have not been observed directly. We show how a conventional motion planner can use the learned terrain model to plan a path to a goal location, using a terrain-specific cost model to accept or reject candidate footholds. In experiments with a real quadruped robot equipped with a laser range finder, we demonstrate the usefulness of our approach and discuss its benefits compared to simpler terrain models such as elevations grids. I.
Towards Engaging Games.

Probabilistic Inductive Logic Programming.
Abstract. In this paper, we present a probabilistic method of dealing with multiclass classification using Stochastic Logic Programs (SLPs), a Probabilistic Inductive Logic Programming (PILP) framework that integrates probability, logic representation and learning. Multi-class prediction attempts to classify an observed datum or example into its proper classification given that it has been tested to have multiple predictions. We apply an SLP parameter estimation algorithm to a previous study in the protein fold prediction area and a multi-class classification working example, in which logic programs have been learned by Inductive Logic Programming (ILP) and a large number of multiple predictions have been detected. On the basis of several experiments, we demonstrate that PILP approaches (eg. SLPs) have advantages for solving multi-class prediction problems with the help of learned probabilities. In addition, we show that SLPs outperform ILP plus majority class predictor in both predictive accuracy and result interpretability. 1
Basic Principles of Learning Bayesian Logic Programs.
Bayesian logic programs tightly integrate definite logic programs with Bayesian networks in order to... In this paper, we present results on combining Inductive Logic Programming with Bayesian networks to learn both the qualitative and the quantitative components of Bayesian logic programs from data. More precisely, we show how the qualitative components can be learned by combining the inductive logic programming setting learning from interpretations with score-based techniques for learning Bayesian networks. The estimation of the quantitative components is reduced to the corresponding problem of (dynamic) Bayesian networks
Relational Sequence Learning.
Abstract. Wetackletheproblemofmulti-classrelational sequencelearning using relevant patterns discovered from a set of labelled sequences. To deal with this problem, firstly each relational sequence is mapped into a feature vector using the result of a feature construction method. Since, the efficacy of sequence learning algorithms strongly depends on the features used to represent the sequences, the second step is to find an optimal subset of the constructed features leading to high classification accuracy. This feature selection task has been solved adopting a wrapper approach that uses a stochastic local search algorithm embedding a naïve Bayes classifier. The performance of the proposed method applied to a real-world dataset shows an improvement when compared to other established methods, such as hidden Markov models, Fisher kernels and conditional random fields for relational sequences.
Social Network Mining with Nonparametric Relational Models.
Abstract. Statistical relational learning (SRL) provides effective techniques to analyze social network data with rich collections of objects and complex networks. Infinite hidden relational models (IHRMs) introduce nonparametric mixture models into relational learning and have been successful in many relational applications. In this paper we explore the modeling and analysis of complex social networks with IHRMs for community detection, link prediction and product recommendation. In an IHRM-based social network model, each edge is associated with a random variable and the probabilistic dependencies between these random variables are specified by the model, based on the relational structure. The hidden variables, one for each object, are able to transport information such that non-local probabilistic dependencies can be obtained. The model can be used to predict entity attributes, to predict relationships between entities and it performs an interpretable cluster analysis. We demonstrate the performance of IHRMs with three social network applications. We perform community analysis on the Sampson’s monastery data and perform link analysis on the Bernard &amp; Killworth data. Finally we apply IHRMs to the MovieLens data for prediction of user preference on movies and for an analysis of user clusters and movie clusters.
Preface.
part of a series of studies in support of the California Governor’s Advisory Committee on Education Excellence. i PREFACE i LIST OF FIGURES iv
Compressing probabilistic Prolog programs.

Mining and Learning with Graphs
Link-based data may be studied formally by means of unordered  trees. On a dataset formed by such link-based data, a natural  notion of support-based closure can be immediately defined. Abstracting  information from subsets of such data requires, first, a formal notion  of intersection; second, deeper understanding of the notion of closure;  and, third, e#cient algorithms for computing intersections on unordered  trees. We provide answers to these three questions.
Most likely heteroscedastic Gaussian process regression.
This paper presents a novel Gaussian process (GP) approach to regression with inputdependent noise rates. We follow Goldberg et al.’s approach and model the noise variance using a second GP in addition to the GP governing the noise-free output value. In contrast to Goldberg et al., however, we do not use a Markov chain Monte Carlo method to approximate the posterior noise variance but a most likely noise approach. The resulting model is easy to implement and can directly be used in combination with various existing extensions of the standard GPs such as sparse approximations. Extensive experiments on both synthetic and real-world data, including a challenging perception problem in robotics, show the effectiveness of most likely heteroscedastic GP regression. 1.
07161 Abstracts Collection %2D%2D Probabilistic

Gaussian Beam Processes A Nonparametric Bayesian Measurement Model for Range Finders.
Abstract — In probabilistic mobile robotics, the development of measurement models plays a crucial role as it directly influences the efficiency and the robustness of the robot’s performance in a great variety of tasks including localization, tracking, and map building. In this paper, we present a novel probabilistic measurement model for range finders, called Gaussian beam processes, which treats the measurement modeling task as a nonparametric Bayesian regression problem and solves it using Gaussian processes. The major benefit of our approach is its ability to generalize over entire range scans directly. This way, we can learn the distributions of range measurements for whole regions of the robot’s configuration space from only few recorded or simulated range scans. Especially in approximative approaches to state estimation like particle filtering or histogram filtering, this leads to a better approximation of the true likelihood function. Experiments on real world and synthetic data show that Gaussian beam processes combine the advantages of two popular measurement models. I.
Fisher Kernels for Relational Data.
Abstract. Combining statistical and relational learning receives currently a lot of attention. The majority of statistical relational learning approaches focus on density estimation. For classification, however, it is well-known that the performance of such generative models is often lower than that of discriminative classifiers. One approach to improve the performance of generative models is to combine them with discriminative algorithms. Fisher kernels were developed to combine them with kernel methods, and have shown promising results for the combinations of support vector machines with (logical) hidden Markov models and Bayesian networks. So far, however, Fisher kernels have not been considered for relational data, i.e., data consisting of a collection of objects and relational among these objects. In this paper, we develop Fisher kernels for relational data and empirically show that they can significantly improve over the results achieved without Fisher kernels. 1
TildeCRF Conditional Random Fields for Logical Sequences.
Abstract. Conditional Random Fields (CRFs) provide a powerful instrument for labeling sequences. So far, however, CRFs have only been considered for labeling sequences over flat alphabets. In this paper, we describe TildeCRF, the first method for training CRFs on logical sequences, i.e., sequences over an alphabet of logical atoms. TildeCRF’s key idea is to use relational regression trees in Dietterich et al.’s gradient tree boosting approach. Thus, the CRF potential functions are represented as weighted sums of relational regression trees. Experiments show a significant improvement over established results achieved with hidden Markov models and Fisher kernels for logical sequences. 1
Robust 3D Scan Point Classification using Associative Markov Networks.
Abstract — In this paper we present an efficient technique to learn Associative Markov Networks (AMNs) for the segmentation of 3D scan data. Our technique is an extension of the work recently presented by Anguelov et al. [1], in which AMNs are applied and the learning is done using max-margin optimization. In this paper we show that by adaptively reducing the training data, the training process can be performed much more efficiently while still achieving good classification results. The reduction is obtained by utilizing kd-trees and pruning them appropriately. Our algorithm does not require any additional parameters and yields an abstraction of the training data. In experiments with real data collected from a mobile outdoor robot we demonstrate that our approach yields accurate segmentations. I.
Relational Sequence Alignments and Logos.

Revising Probabilistic Prolog Programs.
Abstract. The ProbLog (probabilistic prolog) language has been introduced in [1], where various algorithms have been developed for solving and approximating ProbLog queries. Here, we define and study the problem of revising ProbLog theories from examples. 1 ProbLog: Probabilistic Prolog A ProbLog program consists – as Prolog – of a set of definite clauses. However, in ProbLog every clause ci is labeled with the probability pi that it is true. Example 1. Within bibliographic data analysis, the similarity structure among items can improve information retrieval results. Consider a collection of papers {a, b, c, d} and some pairwise similarities similar(a, b), e.g., based on key word analysis. Two items X and Y are related(X, Y) if they are similar (such as a and c) or if X is similar to some item Z which is related to Y. Uncertainty in the data and in the inference can elegantly be represented by the attached probabilities:
Learning Relational Navigation Policies.
Navigation is one of the fundamental tasks for a mobile robot. The majority of path planning approaches has been designed to entirely solve the given problem from scratch given the current and goal configurations of the robot. Although these approaches yield highly efficient plans, the computed policies typically do not transfer to other, similar tasks. We propose to learn relational decision trees as abstract navigation strategies from example paths. Relational abstraction has several interesting and important properties. First, it allows a mobile robot to generalize navigation plans from specific examples provided by users or exploration. Second, the navigation policy learned in one environment can be transferred to unknown environments. In several experiments with real robots in a real environment and in simulated runs, we demonstrate the usefulness of our approach.
Logical Hidden Markov Models.
Logical hidden Markov models (LOHMMs) upgrade traditional hidden Markov models to deal with sequences of structured symbols in the form of logical atoms, rather than flat characters. This note formally introduces LOHMMs and presents solutions to the three central inference problems for LOHMMs: evaluation, most likely hidden state sequence and parameter estimation. The resulting representation and algorithms are experimentally evaluated on problems from the domain of bioinformatics. 1.
An inductive logic programming approach to statistical relational learning.

Logical Hidden Markov Models.
Logical hidden Markov models (LOHMMs) upgrade traditional hidden Markov models to deal with sequences of structured symbols in the form of logical atoms, rather than flat characters. This note formally introduces LOHMMs and presents solutions to the three central inference problems for LOHMMs: evaluation, most likely hidden state sequence and parameter estimation. The resulting representation and algorithms are experimentally evaluated on problems from the domain of bioinformatics. 1.
Towards Learning Stochastic Logic Programs from Proof%2DBanks.
Stochastic logic programs combine ideas from probabilistic grammars with the expressive power of definite clause logic; as such they can be considered as an extension of probabilistic context-free grammars. Motivated by an analogy with learning tree-bank grammars, we study how to learn stochastic logic programs from proof-trees. Using proof-trees as examples imposes strong logical constraints on the structure of the target stochastic logic program. These constraints can be integrated in the least general generalization (lgg) operator, which is employed to traverse the search space. Our implementation employs a greedy search guided by the maximum likelihood principle and failure-adjusted maximization. We also report on a number of simple experiments that show the promise of the approach.
nFOIL Integrating Na%EFve Bayes and FOIL.

%22Say EM%22 for Selecting Probabilistic Models for Logical Sequences.
Many real world sequences such as protein secondary structures or shell logs exhibit a rich internal structures. Traditional probabilistic models of sequences, however, consider sequences of flat symbols only. Logical hidden Markov models have been proposed as one solution. They deal with logical sequences, i.e., sequences over an alphabet of logical atoms. This comes at the expense of a more complex model selection problem. Indeed, different abstraction levels have to be explored. In this paper, we propose a novel method for selecting logical hidden Markov models from data called SAGEM. SAGEM combines generalized expectation maximization, which optimizes parameters, with structure search for model selection using inductive logic programming refinement operators. We provide convergence and experimental results that show SAGEM’s effectiveness. 1
Probabilistic Inductive Logic Programming.
Abstract. In this paper, we present a probabilistic method of dealing with multiclass classification using Stochastic Logic Programs (SLPs), a Probabilistic Inductive Logic Programming (PILP) framework that integrates probability, logic representation and learning. Multi-class prediction attempts to classify an observed datum or example into its proper classification given that it has been tested to have multiple predictions. We apply an SLP parameter estimation algorithm to a previous study in the protein fold prediction area and a multi-class classification working example, in which logic programs have been learned by Inductive Logic Programming (ILP) and a large number of multiple predictions have been detected. On the basis of several experiments, we demonstrate that PILP approaches (eg. SLPs) have advantages for solving multi-class prediction problems with the help of learned probabilities. In addition, we show that SLPs outperform ILP plus majority class predictor in both predictive accuracy and result interpretability. 1
Fisher Kernels for Logical Sequences.
Abstract. One approach to improve the accuracy of classifications based on generative models is to combine them with successful discriminative algorithms. Fisher kernels were developed to combine generative models with a currently very popular class of learning algorithms, kernel methods. Empirically, the combination of hidden Markov models with support vector machines has shown promising results. So far, however, Fisher kernels have only been considered for sequences over flat alphabets. This is mostly due to the lack of a method for computing the gradient of a generative model over structured sequences. In this paper, we show how to compute the gradient of logical hidden Markov models, which allow for the modelling of logical sequences, i.e., sequences over an alphabet of logical atoms. Experiments show a considerable improvement over results achieved without Fisher kernels for logical sequences.
Bellman goes relational.
Motivated by the interest in relational reinforcement  learning, we introduce a novel  relational Bellman update operator called  ReBel. It employs a constraint logic programming  language to compactly represent  Markov decision processes over relational domains.
Logical Markov Decision Programs and the Convergence of Logical TD%28lambda%29.
Recent developments in the area of relational reinforcement  learning (RRL) have resulted in a number of new algorithms. A theory,  however, that explains why RRL works, seems to be lacking. In this paper,  we provide some initial results on a theory of RRL. To realize this,  we introduce a novel representation formalism, called logical Markov decision  programs (LOMDPs), that integrates Markov Decision Processes  (MDPs) with Logic Programs. Using LOMDPs one can compactly and  declaratively represent complex MDPs. Within this framework we then  devise a relational upgrade of TD(#) called logical TD(#) and prove convergence.
Balios %2D The Engine for Bayesian Logic Programs.

Balios %2D The Engine for Bayesian Logic Programs.





Probabilistic logic learning.
The past few years have witnessed an significant interest in probabilistic logic learning, i.e. in research lying at the intersection of probabilistic reasoning, logical representations, and machine learning. A rich variety of di#erent formalisms and learning techniques have been developed. This paper provides an introductory survey and overview of the stateof -the-art in probabilistic logic learning through the identification of a number of important probabilistic, logical and learning concepts.

Logical Hidden Markov Models %28Extendes abstract%29.
Kristian Kersting    Tapani Raiko    Stefan Kramer    Luc De Raedt    Machine Learning Lab, Computer Science Department,  University of Freiburg  Georges-Koehler-Alle 079, 79112 Freiburg, Germany    Laboratory of Computer and Information Science,  Helsinki University of Technology  P.O. Box 540, Helsinki, FIN-02015 HUT, Finland  Keywords: Hidden Markov Models, Probabilistic Modeling, First-Order Logic, Structural Signatures, SCOP  With the growing number of determined protein structures and the availability of classification schemes, it becomes increasingly important to develop computer methods that automatically extract structural signatures for classes of proteins. We present a new Machine Learning technique, Logical Hidden Markov Models (LOHMMs), and apply it to the task of finding structural signatures of folds according to the classification scheme SCOP.
Scaled Conjugate Gradients for Maximum Likelihood An Empirical Comparison with the EM Algorithm.
Abstract. To learn Bayesian networks, one must estimate the parameters of the network from the data. EM (Expectation-Maximization) and gradient-based algorithms are the two best known techniques to estimate these parameters. Although the theoretical properties of these two frameworks are well-studied, it remains an open question as to when and whether EM is to be preferred over gradients. We will answer this question empirically. More specifically, we first adapt scaled conjugate gradients well-known from neural network learning. This accelerated conjugate gradient avoids the time consuming line search of more traditional methods. Secondly, we empirically compare scaled conjugate gradients with EM. The experiments show that accelerated conjugate gradients are competitive with EM. Although, in general EM is the domain independent method of choice, gradient-based methods can be superior. 1 Introduction Bayesian networks are one of the most important, efficient and elegant frameworks for representing and reasoning with probabilistic models. They specify joint probability distributions over finite sets of random variables, and have been applied to many real-world problems in diagnosis, forecasting, automated vision, sensor fusion and manufacturing control. Over the past years, there has been much interest in the problem of learning Bayesian networks from data to avoid the problems of knowledge elicitation. For learning Bayesian networks, parameter estimation is a fundamental task not only because of the inability of humans to reliably estimate the parameters, but also because it forms the basis for the overall learning problem [10].

Adaptive Bayesian Logic Programs.
First order probabilistic logics combine a first order logic with a probabilistic knowledge representation. In this context, we introduce continuous Bayesian logic programs, which extend the recently introduced Bayesian logic programs to deal with continuous random variables. Bayesian logic programs tightly integrate definite logic programs with Bayesian networks. The resulting framework nicely seperates the qualitative (i.e. logical) component from the quantitative (i.e. the probabilistic) one. We also show how the quantitative component can be learned using a gradient-based maximum likelihood method. 
Towards Combining Inductive Logic Programming with Bayesian Networks.
Recently, new representation languages that integrate first order logic with Bayesian networks have been developed. Bayesian logic programs are one of these languages. In this paper, we present results on combining Inductive Logic Programming (ILP) with Bayesian networks to learn both the qualitative and the quantitative components of Bayesian logic programs. More precisely, we show how to combine the ILP setting learning from interpretations with score-based techniques for learning Bayesian networks. Thus, the paper positively answers Koller and Pfeffer&#039;s question, whether techniques from ILP could help to learn the logical component of first order probabilistic models.
Bayesian Logic Programs
Various proposals for combining first order logic with  Bayesian nets exist. We introduce the formalism of  Bayesian logic programs, which is basically a simplification and reformulation of Ngo and Haddawys probabilistic  logic programs. However, Bayesian logic programs  are sufficiently powerful to represent essentially the same knowledge in a more elegant manner. The elegance is illustrated by the fact that they can represent  both Bayesian nets and definite clause programs (as in &#034;pure&#034; Prolog) and that their kernel in Prolog is actually an adaptation of an usual Prolog meta-interpreter.
Bayesian Logic Programs.
Various proposals for combining first order logic with  Bayesian nets exist. We introduce the formalism of  Bayesian logic programs, which is basically a simplification and reformulation of Ngo and Haddawys probabilistic  logic programs. However, Bayesian logic programs  are sufficiently powerful to represent essentially the same knowledge in a more elegant manner. The elegance is illustrated by the fact that they can represent  both Bayesian nets and definite clause programs (as in &#034;pure&#034; Prolog) and that their kernel in Prolog is actually an adaptation of an usual Prolog meta-interpreter.
